/*
  解法：istringstream去掉空格 + reverse翻转单词顺序 + 重新加空格输出
  为什么：无
  时间复杂度：O(n)，空间复杂度：O(n)
 */

#include <iostream>
#include <string>
#include <sstream>		// 用于istringsream类
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
public:
	string reverseWords(string s)
	{
		vector<string> words;
		istringstream iss(s);	//创建一个字符串输入流对象 iss, 并用s初始化
		string word;
		
		// 提取所有单词, 自动跳过前导空白
		while (iss >> word)		//成功读取一个非空单词返回true, 如果读不到就返回false
		{
			words.push_back(word);
		}
		
		// 反转单词顺序
		reverse(words.begin(), words.end());
		
		// 拼接成一个字符串
		string result;
		for (size_t i = 0; i < words.size(); i++)	//size_t无符号整数类型
		{
			result += words[i];
			if (i != words.size() - 1)
			{
				result += " ";
			}
		}
		
		return result;
	}
};

int main()
{
	Solution solution;
	
	string input1 = "  the sky is  blue ";
	string output1 = solution.reverseWords(input1);
	cout << "输入：\"  the sky is  blue \"" << endl;
	cout << "输出：\"" << output1 << "\"" << endl << endl;
	
	string input2 = "   hello world  ";
	string output2 = solution.reverseWords(input2);
	cout << "输入：\"   hello world  \"" << endl;
	cout << "输出：\"" << output2 << "\"" << endl << endl;
	
	string input3 = "a   good   example";
	string output3 = solution.reverseWords(input3);
	cout << "输入：\"a   good   example\"" << endl;
	cout << "输出：\"" << output3 << "\"" << endl;
	
	return 0;
}


